<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>

<body>
  <script>
    var openLock = function (deadends, target) {
      // 记录需要跳过的死亡密码
      let deads = new Set(deadends);
      // 记录已经穷举过的密码，防止走回头路
      let visited = new Set();
      let q = [];
      // 从起点开始启动广度优先搜索
      let step = 0;
      q.push("0000");
      visited.add("0000");

      while (q.length !== 0) {
        let sz = q.length;
        // 将当前队列中的所有节点向周围扩散
        for (let i = 0; i < sz; i++) {
          let cur = q.shift();

          // 判断是否到达终点
          if (deads.has(cur))
            continue;
          if (cur === target)
            return step;

          // 将一个节点的未遍历相邻节点加入队列
          for (let j = 0; j < 4; j++) {
            let up = plusOne(cur, j);
            if (!visited.has(up)) {
              q.push(up);
              visited.add(up);
            }
            let down = minusOne(cur, j);
            if (!visited.has(down)) {
              q.push(down);
              visited.add(down);
            }
          }
        }
        // 在这里增加步数
        step++;
      }
      // 如果穷举完都没找到目标密码，那就是找不到了
      return -1;
    }

    // 将 s[j] 向上拨动一次
    var plusOne = function (s, j) {
      let ch = s.split('');
      if (ch[j] == '9') ch[j] = '0';
      else ch[j] = String.fromCharCode(ch[j].charCodeAt(0) + 1);
      return ch.join('');
    };

    // 将 s[i] 向下拨动一次
    var minusOne = function (s, j) {
      let ch = s.split('');
      if (ch[j] == '0') ch[j] = '9';
      else ch[j] = String.fromCharCode(ch[j].charCodeAt(0) - 1);
      return ch.join('');
    }
  </script>
</body>

</html>